package Binary_tree;

public class Code09_MinHeight {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int x) {
            val = x;
        }
    }

    public static int minHeight1(Node head){
        if (head == null){
            return 0;
        }
        return process1(head);
    }

    public static int process1(Node x){
        if (x.left == null && x.right == null){
            return 1;
        }
        int lH = Integer.MAX_VALUE;
        if (x.left != null){
            lH = process1(x.left);
        }
        int rH = Integer.MAX_VALUE;
        if (x.right != null){
            rH = process1(x.right);
        }
        return Math.min(lH, rH) + 1;
    }
    // 莫里斯遍历，记录层数
    public static int minHeight2(Node head){
        if (head == null){
            return 0;
        }
        Node cur = head;
        Node mostRight = null;
        int curLevel = 0;
        int minHeight = Integer.MAX_VALUE;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                int leftHeight = 1;
                while (mostRight.right != null && mostRight.right != cur){
                    leftHeight++;
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){ // 第一次到达
                    curLevel++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // 第二次到达
                    if (mostRight.left == null){ // 当前mostRight为叶子节点
                        minHeight = Math.min(minHeight, curLevel);
                    }
                    curLevel -= leftHeight; // 从叶子节点回到上层根
                    mostRight.right = null;
                }
            } else { // 左子树没有右子树，只会到达一次
                curLevel++;
            }
            cur = cur.right; // 左边处理完或没有左子树，走右边
        }
        // 考虑最右的节点是否为叶子节点，若是，获取高度
        int finalRight = 1;
        cur = head;
        while (cur.right != null){
            finalRight++;
            cur = cur.right;
        }
        if (cur.left == null && cur.right == null){
            minHeight = Math.min(minHeight, finalRight);
        }
        return minHeight;
    }

    public static void main(String[] args) {
        Node t1 = new Node(1);
        t1.left = new Node(2);
        t1.right = new Node(3);
        t1.left.left = new Node(4);
        t1.left.right = new Node(5);
        t1.right.left = new Node(6);
        t1.right.right = new Node(7);
        System.out.println(minHeight1(t1));
        System.out.println(minHeight2(t1));
    }
}
